package org.algorithm.biubiu.wheel_1.链表;

import java.util.HashMap;

/**
 * @author jiazhaoxin
 * @Date 2022/2/13
 * @Desc
 */
public class LRUCache {


    class CacheNode {
        public int val;
        public int key;
        public CacheNode next;
        public CacheNode prve;

        public CacheNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    HashMap<Integer, CacheNode> map;
    CacheNode head = new CacheNode(-1,-1);
    CacheNode tail = new CacheNode(-1,-1);
    int maxSize;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        maxSize= capacity;
        head.next = tail;
        tail.prve = head;
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        CacheNode node =  map.get(key);
        node.prve.next  = node.next;
        node.next.prve = node.prve;
        moveToTail(node);
        return map.get(key).val;

    }

    public void put(int key, int value) {
        if(get(key)!=-1){
            CacheNode node = map.get(key);
            node.val = value;
            map.put(key,node);
        }else{
            CacheNode node = new CacheNode(key,value);
            if(map.size()>=maxSize){
                CacheNode moveNode = head.next;
                head.next = head.next.next;
                head.next.prve = head;
                map.remove(moveNode.key);
            }
            map.put(key,node);
            moveToTail(node);
        }
    }
    public void moveToTail(CacheNode node){
        tail.prve.next = node;
        node.prve = tail.prve;
        node.next = tail;
        tail.prve = node;
    }
}
